package coalition.formation.combinations;

import java.util.ArrayList;
import java.util.Collection;
//import java.util.HashMap;
import java.util.List;
import java.util.Vector;

public class Combination {

	//private static final boolean USE_MEMOIZATION = false;
	
    private Combination()
    {
        super();
    }
    
    //private static HashMap<Integer, HashMap<Integer, List<int[]>>> foundCombinations = new HashMap<Integer, HashMap<Integer, List<int[]>>>();
	
    public static <T extends Comparable<? super T>> List<List<T>> findCombinations(Collection<T> elements){
  
    	List<List<T>> result = new ArrayList<List<T>>();
        
        for (int i = 0; i <= elements.size(); i++)
            result.addAll(findCombinations(elements, i));

        return result;    	
    	
    }
 
    public static <T extends Comparable<? super T>> List<List<T>> findCombinations(Collection<T> elements, int n)
    {    
    	if(n > elements.size()) throw new IllegalArgumentException("combination size cannot exceed set size");
    	
        if (n == 0)
        {
        	List<List<T>> result = new ArrayList<List<T>>();
            result.add(new ArrayList<T>());
            return result;
        }
        //ArrayList<T> elementArray = new ArrayList<T>();
        Vector<T> elementsList = new Vector<T>();
        elementsList.addAll(elements);
        List<int[]> combinations = findCombinations(n, elements.size());
        List<List<T>> result = convertListOfIntegerArraysToListOfListOfT(elementsList, combinations);
    	return result;
    	
    }
    
    private static <T extends Comparable<? super T>> List<List<T>> convertListOfIntegerArraysToListOfListOfT(List<T> elementsList, List<int[]> combinations){
    	Vector<List<T>> result = new Vector<List<T>>(combinations.size());
    	for(int[] combination : combinations){
    		result.add(convertIntegerArrayToListOfT(elementsList, combination));
    	}
    	return result;
    }
    
    private static <T extends Comparable<? super T>> List<T> convertIntegerArrayToListOfT(List<T> elementsList, int[] combination){
    	Vector<T> result = new Vector<T>(combination.length);
    	for(Integer element : combination){
    		result.add(elementsList.get(element));
    	}
    	return result;    	
    }
    
    public static List<int[]> findCombinations(int setSize){
    	  
    	List<int[]> result = new ArrayList<int[]>();
        
        for (int i = 0; i <= setSize; i++)
            result.addAll(findCombinations(i, setSize));

        return result;    	
    	
    }    
    
    public static List<int[]> findCombinations(int combinationSize, int setSize){
    	
    	List<int[]> result = new ArrayList<int[]>();
    	
    	int[] firstCombination = getFirstCombination(combinationSize, setSize);
    	result.add(firstCombination);
    	//System.out.println("got first combination");
    	int[] lastCombination = firstCombination;
    	while(true){
    		int[] nextCombination = getNextCombination(lastCombination, setSize);
    		if(nextCombination == null) break;
    		lastCombination = nextCombination;
    		result.add(nextCombination);
    	}    	
    	return result;
    }
    
    /*
    public static List<int[]> findCombinationsByMemoization(int combinationSize, int setSize){
    	
    	HashMap<Integer, List<int[]>> combinationsBySetSize = foundCombinations.get(setSize);
    	if(combinationsBySetSize != null){
    		List<int[]> combinations = combinationsBySetSize.get(combinationSize);
    		if(combinations != null)
    			return combinations;
    	}
    	List<int[]> result = findCombinations(combinationSize, setSize);
    	
    	if(combinationsBySetSize != null){
    		combinationsBySetSize.put(combinationSize, result);
    	} else{
    		HashMap<Integer, List<int[]>> combinations = new HashMap<Integer, List<int[]>>();
    		combinations.put(combinationSize, result);
    		foundCombinations.put(setSize, combinations);
    	}
    	return result;
    }
    */
    
    private static int[] getNextCombination(int[] indices, int setSize){
    	
    	//find next combination in lexicographic order
    	//all combinations satisfy property that their elements are
    	//strictly increasing; this ensure uniqueness and allows
    	//a method to construct them from "previous" ones
    	
    	//int[] nextCombination = new int[indices.length];
    	int combinationSize = indices.length;
    	int currentPosition = combinationSize - 1;	//start at last index
    	while(true){
    		//if we have run off the array, there is no possible increment
    		if(currentPosition < 0) return null;    		
    		//look for an index that can be incremented
    		//indices can be incremented as long as
    		//1)their value is less than the setSize
    		//2)their new value is small enough so that all the following indices are distinct and
    		//larger
    		int indexAtCurrentPosition = indices[currentPosition];
    		//check to see if the current index value is smaller than the set size
    		//remembering that the indices start at zero, so for a set size
    		//of n, the maximum should be n-2, for it to be incremented
    		if(indexAtCurrentPosition >= setSize - 1
    				|| indexAtCurrentPosition >= setSize - (combinationSize - currentPosition)
    				//use sometimes redundant short circuit logic here
    				//first check to see we are not incrementing index to a value
    				//not in the set of values, than check to see we are not incrementing it to a value that
    				//would make completing the list in a strictly increasing way impossible
    		){
    			//look at the next position to the left
    			currentPosition--; continue;
    		}
    		//testing to make sure that the would be incremented index value would not
    		//equal the value to its right is redundant since the check that enough elements
    		//greater than the incremented index are available to complete the list, is the same
    		//by induction from the end of the string
    		//if(currentPosition == combinationSize - 1 ||
    		//		indexAtCurrentPosition >= indices[currentPosition + 1]){
    		//	return null;
    		//}
    		int[] result = getIntArrayWithOneElementIncremented(indices, currentPosition, setSize);
    		//System.out.println(printIntArray(result));
    		return result;
    	}
    }
    
    private static int[] getFirstCombination(int combinationSize, int setSize){
    	if(combinationSize > setSize) throw new IllegalArgumentException("combination size cannot exceed set size");
    	int[] result = new int[combinationSize];
    	for(int i = 0; i < combinationSize; i++){
    		result[i] = i;
    	}
    	return result;
    }
    
    private static int[] getIntArrayWithOneElementIncremented(int[] a, int index, int setSize){
    	int size = a.length;
    	if(index >= size) throw new IllegalArgumentException("illegal index specified for replacement");
    	if(size >= setSize) throw new IllegalArgumentException("combination size cannot exceed set size");
    	if(a[index] >= setSize - (size - index) ) 
    		throw new IllegalArgumentException("index value exceeds limit for legal ordered combination");
    	int[] result = new int[size];
    	//up until index element, use same values as before
    	for(int i = 0; i < index; i++){
    		result[i] = a[i];
    	}
    	//increment index element
    	int indexValue = a[index] + 1;
    	result[index] = indexValue;
    	//set following values to be increasing from index element
    	//this is the smallest value lexicographically for the sublist following
    	//the index element
    	for(int i = 1; index + i < size; i++){
    		result[index + i] = indexValue + i;
    	}    	
    	
       	//for(int i = index; i < a.length; i++){
    	//	if(result[i] > setSize -1)
    	//		throw new IllegalArgumentException("illegal index in incremented combination");
    	//}        	
    	
    	return result;
    }
 
}
